package momo.multitree.algo;

import momo.multitree.structure.*;

import java.io.FileReader;
import java.io.StringReader;
import java.util.HashMap;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import junit.framework.TestCase;


public class CostLastTreeTest extends TestCase {
	Log log = LogFactory.getLog(CostLastTreeTest.class);
	
	protected void setUp() throws Exception {
		super.setUp();
	}

	protected void tearDown() throws Exception {
		super.tearDown();
	}

	/*
	public void testMalicious2() throws Exception {
		//Graph g = new Graph(new FileReader("dataset/5_node_easy_symmetric_dataset_53.txt"));
		String desc = "5\n 0, 0.2, 0.6943805000808616, Site ID: 0 \n"+
		"1, 0.0, 0.003240120852563644, Site ID: 1\n" +
		"2, 0.2, 0.20269136513473485, Site ID: 2\n" +
		"3, 0.2, 0.538759842168255, Site ID: 3\n" +
		"4, 0.4, 0.18159505457884806, Site ID: 3\n" +
		"7\n" +
		"0, 4, 3, 0.0, 0.0, 5.0, 5.0, Leaf Edges of Site 3\n" +
		"1, 0, 1, 21.0, 21.0, 133.0, 133.0, WAN Edges of Site\n" +
		"2, 0, 2, 16.0, 16.0, 239.0, 239.0, WAN Edges of Site\n" +
		"3, 0, 3, 28.0, 28.0, 482.0, 482.0, WAN Edges of Site\n" +
		"4, 1, 2, 11.0, 11.0, 231.0, 231.0, WAN Edges of Site\n" +
		"5, 1, 3, 16.0, 16.0, 313.0, 313.0, WAN Edges of Site\n" +
		"6, 2, 3, 18.0, 18.0, 128.0, 128.0, WAN Edges of Site\n" +
		"#Seed No: 6861842016361387952";
	
		Graph g = new Graph(new StringReader(desc));
		CostLastTree clt = new CostLastTree(g, g.getNode("4"));
		Tree lastTree = clt.makeLast();
		log.debug("lastTree"+lastTree);
		
		assertEquals(55.4, lastTree.compCost(), 0.0000001);
	}
	*/
	
	public void testMalicious() throws Exception {
		String desc = "5\n" +
				"0, 0.0, 0.47547793433606467, Site ID: 0\n" +
				"1, 0.4, 0.46532902325999803, Site ID: 1\n" +
				"2, 0.0, 0.40399051600722824, Site ID: 2\n" +
				"3, 0.6, 0.32057876662143225, Site ID: 3\n" +
				"4, 0.0, 0.9435513889955225, Site ID: 3\n" +
				"7\n" +
				"0, 4, 3, 0.0, 0.0, 10.0, 10.0, Leaf Edges of Site 3\n" +
				"1, 0, 1, 14.0, 14.0, 441.0, 441.0, WAN Edges of Site\n" +
				"2, 0, 2, 19.0, 19.0, 424.0, 424.0, WAN Edges of Site\n" +
				"3, 0, 3, 16.0, 16.0, 459.0, 459.0, WAN Edges of Site\n" +
				"4, 1, 2, 15.0, 15.0, 268.0, 268.0, WAN Edges of Site\n" +
				"5, 1, 3, 18.0, 18.0, 417.0, 417.0, WAN Edges of Site\n" +
				"6, 2, 3, 20.0, 20.0, 485.0, 485.0, WAN Edges of Site\n" +
				"#Seed No: 7246914281425875970";
	
		
		Graph g = new Graph(new StringReader(desc));
		
		CostLastTree clt = new CostLastTree(g, g.getNode("4"));
		Tree lastTree = clt.makeLast();
		log.debug("lastTree: "+lastTree);
		
		
		assertEquals(54.2, lastTree.compCost(), 0.00001);
		
	}

	public void testComputeDistances() {
		Node a = new Node("0", 0.125, 1);
		Node b = new Node("1", 0.125, 1);
		Node c = new Node("2", 0.125, 1);
		Node d = new Node("3", 0.125, 1);
		Node e = new Node("4", 0.125, 1);
		Node f = new Node("5", 0.125, 1);
		Node g = new Node("6", 0.125, 1);
		Node h = new Node("7", 0.125, 1);
		
		Edge ab = new Edge("0", a, b, 4, 4, 1, 1);
		Edge bc = new Edge("1", b, c, 3, 3, 1, 1);
		Edge ag = new Edge("2", a, g, 5, 5, 1, 1);
		Edge bd = new Edge("3", b, d, 2, 2, 1, 1);
		Edge ch = new Edge("4", c, h, 4, 4, 1, 1);
		Edge de = new Edge("5", d, e, 1, 1, 1, 1);
		Edge df = new Edge("6", d, f, 1, 1, 1, 1);
		Edge ef = new Edge("7", e, f, 1, 1, 1, 1);
		Edge eg = new Edge("8", e, g, 2, 2, 1, 1);
		Edge fh = new Edge("9", f, h, 2, 2, 1, 1);
		Edge gh = new Edge("10", g, h, 1, 1, 1, 1);
		
		Graph gr = new Graph();
		gr.add(a);
		gr.add(b);
		gr.add(c);
		gr.add(d);
		gr.add(e);
		gr.add(f);
		gr.add(g);
		gr.add(h);
		gr.add(ab);
		gr.add(bc);
		gr.add(ag);
		gr.add(bd);
		gr.add(ch);
		gr.add(de);
		gr.add(df);
		gr.add(ef);
		gr.add(eg);
		gr.add(fh);
		gr.add(gh);
		
		Tree mst = new PrimMinSpanTree().mstCostTree(gr, a);
		
		CostLastTree clt = new CostLastTree(gr, a);
		
		HashMap<Node, Double> distances = clt.computeDistances(mst);
		
		assertEquals(0, distances.get(a), 0.00000001);
		assertEquals(4, distances.get(b), 0.00000001);
		assertEquals(7, distances.get(c), 0.00000001);
		assertEquals(6, distances.get(d), 0.00000001);
		assertEquals(7, distances.get(e), 0.00000001);
		assertEquals(7, distances.get(f), 0.00000001);
		assertEquals(9, distances.get(g), 0.00000001);
		assertEquals(10, distances.get(h), 0.00000001);
		
	}

	public void testSwitchSptPath() {
		Node[] n = new Node[] { new Node("0", 0.125, 1), new Node("1", 0.125, 1), new Node("2", 0.125, 1), 
				new Node("3", 0.125,1), new Node("4", 0.125, 1), new Node("5", 0.125, 1), new Node("6", 0.125, 1),
				};
		Edge[] e = new Edge[] { new Edge("0", n[0], n[1], 1, 1, 1, 1),
				new Edge("1", n[0], n[2], 1,1,1,1),
				new Edge("2", n[1], n[3], 10, 10, 1,1),				
				new Edge("3", n[3], n[4], 2, 2, 1,1),
				new Edge("4", n[4], n[5], 3, 3, 1,1),
				new Edge("5", n[4], n[6], 3, 3, 1,1),
				new Edge("6", n[4], n[0], 5, 5, 1,1)};
		Graph g = new Graph();
		for (Node node : n)
			g.add(node);
		for (Edge edge : e) {
			if (edge != e[6])
				g.add(edge);
		}
		Tree t = new Tree(n[0], g);
		
		g.add(e[6]);
		
		CostLastTree clt = new CostLastTree(g, n[0]);
		HashMap<Node, Double> distances = clt.computeDistances(t);
		
		clt.addToSptPath(t, n[6], distances);
		
		assertEquals(null, t.getParent(n[0]));
		assertEquals(n[0], t.getParent(n[1]));
		assertEquals(n[0], t.getParent(n[2]));
		assertEquals(n[4], t.getParent(n[3]));
		assertEquals(n[0], t.getParent(n[4]));
		assertEquals(n[4], t.getParent(n[5]));
		assertEquals(n[4], t.getParent(n[6]));
	}
	
	public void testCheckSpt() {
		Node[] n = new Node[] { new Node("0", 0, 1), new Node("1", 0, 1), new Node("2", 0, 1), 
				new Node("3", 0, 1), new Node("4", 0, 1), new Node("5", 0, 1), new Node("6", 1, 1),
				};
		Edge[] e = new Edge[] { new Edge("0", n[0], n[1], 1, 1, 1, 1),
				new Edge("1", n[1], n[2], 1, 1, 1, 1),
				new Edge("2", n[2], n[3], 1, 1, 1, 1),
				new Edge("3", n[3], n[4], 1, 1, 1, 1),
				new Edge("4", n[4], n[5], 1, 1, 1, 1),
				new Edge("5", n[5], n[6], 1, 1, 1, 1),
				new Edge("6", n[0], n[6], 1, 1, 1, 1),
		};
		Graph g = new Graph();
		for (Node node : n)
			g.add(node);
		for (Edge edge : e)
			g.add(edge);
		
		CostLastTree clt = new CostLastTree(g, n[0]);
		Tree lastTree = clt.makeLast();
		
		assertEquals(null, lastTree.getParent(n[0]));
		assertEquals(n[0], lastTree.getParent(n[1]));
		assertEquals(n[1], lastTree.getParent(n[2]));
		assertEquals(n[2], lastTree.getParent(n[3]));
		assertEquals(n[5], lastTree.getParent(n[4]));
		assertEquals(n[6], lastTree.getParent(n[5]));
		assertEquals(n[0], lastTree.getParent(n[6]));

	}

}
